package middle;

/**
 * 给定一个长度为 n 的环形整数数组nums，返回nums的非空 子数组 的最大可能和。
 *
 * 环形数组意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i]的前一个元素是 nums[(i - 1 + n) % n] 。
 *
 * 子数组 最多只能包含固定缓冲区nums中的每个元素一次。形式上，对于子数组nums[i], nums[i + 1], ..., nums[j]，不存在i <= k1, k2 <= j其中k1 % n == k2 % n。
 *
 * 链接：https://leetcode.cn/problems/maximum-sum-circular-subarray
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class MaximumSumCircularSubarray {
    /**
     * 时间:6ms 超过52%
     * 这个看了一个网友的解答，真的十分的巧妙
     * 链接：https://t.hk.uy/bhkH
     * 举个例子吧，有如下数组 [4,8,-2,6,-7,9] 我们可以知道最大子数组为[4,8,-2,6] 和 [9]两个部分组成的
     * 其中-7就将这个数组分成了三部分[4,8,-2,6] 和 [9]和[-7]
     * 网友的解答中，证明了[-7]这部分是最小子数组。
     * 所以整个数组划分的三个部分为：最大子数组的前半部分、最小子数组、最大子数组的后半部分
     * 也就可以得出，最大子数组=数组总和-最小子数组
     *
     * 其余的内容看原贴吧，打字描述太难了，idea也不能插图片啊
     * */
    class Solution {
        public int maxSubarraySumCircular(int[] nums) {
            int max = nums[0];
            int min = nums[0];
            int total = 0;
            int dpMax = 0;
            int dpMin = 0;
            for (int num : nums) {
                total += num;
                dpMax = Math.max(dpMax + num, num);
                dpMin = Math.min(dpMin + num, num);
                max = Math.max(dpMax, max);
                min = Math.min(dpMin, min);
            }
            return max < 0 ? max : Math.max(total - min, max);
        }
    }
}
